The generation of cryptographic keys for the RSA cryptosystem comprises especially the determining of two prime numbers, denoted as p and q, which define a part of the public key, namely the number N which is the product of these two prime numbers (i.e. N=pq).
In order to ensure that the RSA keys generated are of a sufficient level of security, it is necessary to use a device that generates a random variable r, possessing sufficiently great entropy, used in combination with methods for generating keys (such as for example those specified in the IEEE P1363, ANSI X9.31 and FIPS 186-3 standards).
Even though the private keys thus generated are supposed to ensure a level of security (because they are generated by the application of algorithms validated by the scientific community), there are nevertheless certain flaws. In particular, there is vulnerability that can be related to the presence of a same prime number in several of the moduli generated.
The frequency of appearance of a same prime number in the generation of several moduli is theoretically very low. However, a bug in a computer program or in a piece of hardware of the generating device can induce this type of behavior, whether erratically or not, during the generation of a plurality of RSA keys.
Such a problem can also arise when creating cryptographic keys for variants of RSA cryptosystems, such as for example the Koyama scheme (described in Kuwakado et al, “A new RSA type scheme based on singular cubic curves y2=x3+bx2 mod n” in Annals of the IEICE conference 1996) and other variants proposed by Boneh et al in “Fast Variants of RSA”, such as the RSA using at least three prime numbers to define a public modulus (“Multi-prime RSA”) and the Takagi scheme using a public modulus of the following form: N=ptq, where p and q are prime numbers and t is an integer greater than or equal to 2.
In order to mitigate these problems, a first technique proposed by An Juels and Jorge Guajardo in “RSA Key Generation with Verifiable Randomness” in the Annals of the PKS conference 2002, consists of the use of a zero-knowledge disclosure protocol.
However, this technique is complex to implement and does not provide for a generic solution (i.e. a solution that can easily be adapted to variants of the RSA cryptosystem). Furthermore, in such a technique, the generation of keys requires the distribution of the computations among a plurality of devices and, in addition, the performance of data exchanges which slow down the process for generating keys.